#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-08-25 8:48 上午
# @Author  : yangdy
# @File    : 2020-08-25.491.递增子序列
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        ans = []
        if not nums:
            return ans
        ln = len(nums)

        def dfs(x, n, data):
            if len(data) > 1:
                ans.append(data)
            ss = set()
            for i in range(x, n):
                if (data == [] or nums[i] >= data[-1]) and nums[i] not in ss:
                    ss.add(nums[i])
                    dfs(i+1, n, data+[nums[i]])

        dfs(0, ln, [])
        return ans
        # ss = [True for i in range(ln)]
        # dp = [[]]
        # for i in range(1, ln):
        #     now = []
        #     j = i-1
        #     while j > 0 and nums[j] != nums[i]:
        #         j -= 1
        #     while j < i:
        #         if nums[j] <= nums[i]:
        #             for dpi in dp[j]:
        #                 now.append(dpi + [nums[i]])
        #         # if nums[j] < nums[i]:
        #             if nums[j] == nums[i]:
        #                 if ss[j]:
        #                     now.append([nums[j], nums[i]])
        #                 ss[i] = False
        #             else:
        #                 now.append([nums[j], nums[i]])
        #         j += 1
        #     dp.append(now)
        #
        # def check(data, data_list):
        #     ld = len(data)
        #     for di in data_list:
        #         li = len(di)
        #         if ld != li:
        #             continue
        #         p = True
        #         for ii in range(li):
        #             if data[ii] != di[ii]:
        #                 p = False
        #                 break
        #         if p:
        #             return False
        #     return True
        # ans0 = []
        # for dpi in dp:
        #     ans0 += dpi
        # print('111')
        # for ai in ans0:
        #     if check(ai, ans):
        #         ans.append(ai)
        return ans


questions = [
    ([4, 6, 7, 7],),
    ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 1, 1, 1], ),
    ([1, 1, 1, 2, 2, 2, 3, 3, 3], ),
    ([1, 1, 2, 2], ),
    ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], ),
]

work(questions, lambda q: Solution().findSubsequences(q[0]))

